/*
 * LinkedQueue.java
 *
 * Version:
 *  $Id: LinkedQueue.java 2 2011-03-29 07:21:11Z jhaberstro $
 *
 *
 * Revisions:
 *  $Rev: 2 $
 *
 */

/**
 * A priority queue implemented with a linked list.
 * @author jhaberstro
 * @param <T>
 */
public class LinkedQueue< T extends Comparable< T > > implements PriorityQueue< T >
{
    /**
     * A node of the linked list
     */
    private class LinkedNode
    {
        public LinkedNode() {
            value_ = null;
            next_ = null;
        }
        
        public LinkedNode(T value) {
            value_ = value;
            next_ = null;
        }
        
        public T value_;
        public LinkedNode next_;
    }


    /**
     * Default constructor
     */
    public LinkedQueue() {
        head_ = null;
    }
    
   /**
    *
    * Removes and returns the item at the front of the queue
    *
    * @return T the item at the front of the queue otherwise
    * returns a null
    */
    public T dequeue() {
        if (isEmpty()) {
            return null;
        }
        
        T result = head_.value_;
        head_ = head_.next_;
        return result;
    }

    /**
     * Add an item to the queue at the appropriate location
     * @param toInsert
     */
    public void enqueue(T toInsert) {
        if (head_ == null) {
            head_ = new LinkedNode(toInsert);
        }
        else {
        	LinkedNode previous = null;
            LinkedNode current = head_;
            while (current != null) {
                if (toInsert.compareTo(current.value_) > 0) {
                    T old = current.value_;
                    current.value_ = toInsert;
                    if (current.next_ == null) {
                        current.next_ = new LinkedNode(old);
                    }
                    else {
                        LinkedNode oldNext = current.next_;
                        current.next_ = new LinkedNode(old);
                        current.next_.next_ = oldNext;
                    }
                    
                    return;
                }
                
                previous = current;
                current = current.next_;
            }
            
            previous.next_ = new LinkedNode(toInsert);
        }
    }

    /**
     * Is there anything in the queue?
     * @return
     */
    public boolean isEmpty() {
        return head_ == null;
    }

    /**
     * main method - used here as a test program
     * @param args
     */
    public static void main (String args[] ) {
	    // Test from HeapQueue
	    {
	        LinkedQueue<String> pq = new LinkedQueue<String> ();
    	    pq.enqueue ("Hi");
    	    pq.enqueue ("Hi There");
    	    pq.enqueue ("Apple");
    	    pq.enqueue ("House");
    	    pq.enqueue ("Dog");
        	    
    	    while (!pq.isEmpty()) {
    		    System.out.println (pq.dequeue());
    	    }
	    }
	    
	    // Test 1
	    {
	        LinkedQueue< String > pq = new LinkedQueue< String >();
	        assert (pq.isEmpty());
	        pq.enqueue("A");
	        pq.enqueue("B");
	        pq.enqueue("C");
	        assert (pq.dequeue().equals("C"));
	        assert (pq.dequeue().equals("B"));
	        assert (pq.dequeue().equals("A"));
	        assert (pq.isEmpty());
	    }
	    
	    // Test 2
	    {
	        LinkedQueue< String > pq = new LinkedQueue< String >();
	        assert (pq.isEmpty());
	        pq.enqueue("C");
	        pq.enqueue("B");
	        pq.enqueue("A");
	        assert (pq.dequeue().equals("C"));
	        assert (pq.dequeue().equals("B"));
	        assert (pq.dequeue().equals("A"));
	        assert (pq.isEmpty());
	    }	    
	}
	
   /**
	* The underlying linked list's head
	*/
	private LinkedNode head_;
}